GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Ellipsoidmethode</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Ellipsoidmethode</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Die <b>Ellipsoidmethode</b> ist ein <a href="Polynomialzeit" title="Polynomialzeit">polynomialer</a> <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur <a href="Lineare_Optimierung" title="Lineare Optimierung">Linearen Optimierung</a>. Sie wurde ursprünglich in den Jahren 1976 und 1977 von <a href="David_Yudin" class="mw-redirect" title="David Yudin">David Yudin</a> und <a href="Arkadi_Nemirovski" title="Arkadi Nemirovski">Arkadi Nemirovski</a> und unabhängig davon von <a href="Naum_Schor" title="Naum Schor">Naum Schor</a> zur Lösung <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexer Optimierungsprobleme</a> entwickelt. Im Jahre 1979 wurde sie vom russischen Mathematiker <a href="Leonid_Khachiyan" class="mw-redirect" title="Leonid Khachiyan">Leonid Khachiyan</a> zum ersten <a href="Polynomialzeit" title="Polynomialzeit">polynomialen</a> Algorithmus zur Lösung linearer Programme erweitert. Damit bewies er erstmals die polynomiale Lösbarkeit linearer Optimierungsprobleme. Für praktische Zwecke ist die Ellipsoidmethode allerdings nicht geeignet, da sie dem <a href="Simplex-Verfahren" title="Simplex-Verfahren">Simplex-Verfahren</a> numerisch in der Praxis weit unterlegen ist.

</p><p>Die Ellipsoidmethode ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur Entscheidung, ob ein volldimensionales <a href="Polyeder" title="Polyeder">Polyeder</a> der Form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b\}}">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e007898c47a0cc331afd76447780aee5d2b766e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.342ex; height:2.843ex;" alt="{\displaystyle P=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b\}}" loading="lazy"></span>, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> eine reelle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\times n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/12b23d207d23dd430b93320539abbb0bde84870d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.276ex; height:1.676ex;" alt="{\displaystyle m\times n}" loading="lazy"></span>-<a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ed095b97ebc9bf2aa25047f450e4deb402b8ac47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.361ex; height:2.509ex;" alt="{\displaystyle x,b}" loading="lazy"></span> dimensionskompatible <a href="Vektor" title="Vektor">Vektoren</a> sind, leer ist oder nicht. Falls das Polyeder einen Punkt enthält, dann gibt die Methode auch einen solchen aus. Man kann zeigen, dass dieses Problem äquivalent zum Finden der Optimallösung eines linearen Programms ist.

</p>

<p>Der Algorithmus funktioniert folgendermaßen:

</p>

<ol><li>Es wird ein <a href="Ellipsoid" title="Ellipsoid">Ellipsoid</a> (im Bild rot) bestimmt, welches – falls <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> (im Bild blau) nicht leer ist – einen Punkt des Polyeders enthält. Man kann dabei eine hinreichend große Kugel wählen, die alle möglichen Ecken von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> enthalten muss. Deren maximale Koordinaten und damit der notwendige Radius der Kugel lässt sich durch Lösung von <a href="Lineares_Gleichungssystem" title="Lineares Gleichungssystem">linearen Gleichungssystemen</a> mit Einträgen aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> bestimmen.</li>

<li>Bestimmung einer maximalen <a href="Iteration" title="Iteration">Iterationsanzahl</a> für folgende Schritte:</li>

<li>Es wird getestet, ob das Zentrum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"></span> (im Bild der rote Punkt) des Ellipsoids im Polyeder liegt (also <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Az\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Az\leq b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bb8bb9853dc848917bf85f3fe870e89dd86b10bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.927ex; height:2.343ex;" alt="{\displaystyle Az\leq b}" loading="lazy"></span>)</li>

<li>Falls ja, wird <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"></span> ausgegeben und der Algorithmus ist beendet.</li>

<li>Falls nein, sucht man eine Ungleichung (Schnittebene), die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"></span> vom Polyeder trennt. Dies kann zum Beispiel eine Zeile <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span> der Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> sein, die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}z>b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}z>b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61da0c7f8480d66f3366b608ea3fa4dbce6f312a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.013ex; height:2.509ex;" alt="{\displaystyle a_{i}z>b_{i}}" loading="lazy"></span> erfüllt.</li>

<li>In dem Halbraum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{x\in R^{n}\;|\;a_{i}(x-z)\leq 0\}}">

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{x\in R^{n}\;|\;a_{i}(x-z)\leq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/38cd17975d4bf9acb69356a6f30c5bb5fabf7907.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.773ex; height:2.843ex;" alt="{\displaystyle \{x\in R^{n}\;|\;a_{i}(x-z)\leq 0\}}" loading="lazy"></span> liegt, falls das Polyeder nicht leer ist, ein Punkt von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span>. Nun sucht man ein Ellipsoid (im Bild grün), das möglichst klein ist, aber den Schnitt dieses Halbraums mit dem ursprünglichen Ellipsoid enthält.</li>

<li>Ist die maximale Iterationszahl erreicht, ohne dass ein Ellipsoidzentrum im Polyeder lag, ist dieses leer. Andernfalls macht man wieder bei 3. weiter.</li></ol>

<p>Die maximale Iterationsanzahl berechnet sich polynomial aus der Länge der Binärcodierung der Matrix A und des Vektors b. Dieses Abbruchkriterium beruht darauf, dass das untersuchte Polyeder eine Mindestgröße haben muss, die von der Kodierungslänge von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> abhängt. Wird diese Mindestgröße vom aktuellen Ellipsoid unterschritten, muss das Polyeder leer sein.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Korte, Bernhard; Vygen, Jens: <i>Kombinatorische Optimierung</i>, Springer Berlin Heidelberg, 2008. ISBN 978-3-540-76918-7, S. 79–107</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2019-11-26" href="https://de.wikipedia.org/wiki/?title=Ellipsoidmethode&oldid=194405696">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>